package zijie;

public class backToZero2 {
    // dp[i][j] 表示 用j步骤 走到第i个位置的方法数
    public int backToZero2(int n, int step){
        if(n == 0) return 1;
        if(n == 2) {
            if(step%2 == 0){
                return 1;
            }else{
                return 0;
            }
        }
        int[][] dp = new int[n][step];
        dp[0][0] = 1;
        dp[0][1] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j < step; j++) {
                dp[i][j] = dp[(i + 1)/n][j - 1] + dp[(i - 1 + n)/n][j - 1];
            }
        }

        return dp[0][step];

    }
}
